package 剑指offer;

import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Scanner;
import java.util.Stack;

/** 

* @author ：soulstones
* @version ：2019年9月30日 下午9:56:24 
* @Description：
* 
一个整型数组里除了两个数字之外，其他的数字都出现了两次。
请写程序找出这两个只出现一次的数字。
*/
public class A40数组当中只出现一次的数字 {

	//位运算的运用
	//位运算中异或的性质：两个相同数字异或=0，一个数和0异或还是它本身。

	//当只有一个数出现一次时，我们把数组中所有的数，依次异或运算，最后剩下的就是落单的数，因为成对儿出现的都抵消了。
	 public static void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
		 
		 //这里传入的num1[],num2[]是用来接收只出现一次的值
		int num = 0;
		for (int i = 0; i < array.length; i++) {
			num ^= array[i];   // 所有数异或，结果为不同的两个数字的异或
		}
		int count = 0;// 标志位，记录num中的第一个1出现的位置
		for (; count < array.length; count++) {
			if ((num & (1 << count)) != 0) {
				break;
			}
		}
		num1[0] = 0;
		num2[0] = 0;
		for (int i = 0; i < array.length; i++) {
			if ((array[i] & (1 << count)) == 0) {// 标志位为0的为一组，异或后必得到一个数字（这里注意==的优先级高于&，需在前面加（））
				num1[0] ^= array[i];
			} else {
				num2[0] ^= array[i];// 标志位为1的为一组
			}
		}
		System.out.println(num1[0]+" "+num2[0]);
	}
	 
	 /*
1.  Arrays.sort 数组排序
2、使用栈进行从小到大入栈，一样的则弹出，不一样则入栈
3、取栈中剩余的元素
	  */
	 public static void FindNumsAppearOnce11(int [] array,int num1[] , int num2[]) {
		 Arrays.sort(array);
		 Stack<Integer> stack = new Stack<>();
		 
		 for (int i = 0; i < array.length; i++) {
			if (stack.empty() ||stack.peek()!=array[i]) {
				stack.push(array[i]);                              //不同的才入栈
			}else if (stack.peek()==array[i]) {
				stack.pop();                             //遇到相同的就出栈
			} 
		}
		num1[0]= stack.pop();
		num2[0]=stack.pop();
		System.out.println(num1[0]+" "+num2[0]);
	 }
	 
	 //HashSet的不存在重复值的特性
	 public static void FindNumsAppearOnce22(int [] array,int num1[] , int num2[]) {
		 HashSet<Integer> set = new HashSet<>();
		 for (int i = 0; i < array.length; i++) {
			if (set.contains(array[i])) {               //存在重复
				set.remove(array[i]);
			}else {
				set.add(array[i]);
			}
		}
//遍历HashSet，用iterator
		Iterator<Integer> it = set.iterator();
		if (it.hasNext())
			num1[0] = it.next();
		if (it.hasNext())
			num2[0] = it.next();
		System.out.println(num1[0] + " " + num2[0]);
	}
	 
	 //HashMap也可以实现，存在重复值，就给它的value+1,那么不存在重复值的value就是1了。
	 public static void FindNumsAppearOnce33(int [] array,int num1[] , int num2[]) {
		 HashMap<Integer, Integer> map = new HashMap<>();
		 for (int i = 0; i < array.length; i++) {
			if (map.containsKey(array[i])) {         //存在重复值
				Integer time = map.get(array[i]);
				map.put(array[i], ++time);
			}else {
				map.put(array[i], 1);
			}
		}
		 
		 int count=0;
		 for (int i = 0; i < array.length; i++) {
			if (map.get(array[i])==1) {
				if (count==0) {
					num1[0]=array[i];
					count++;
				}else {
					num2[0]=array[i];
				}
			}
		}
		 System.out.println(num1[0] + " " + num2[0]);
	 }
	 
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		String s = scanner.nextLine();
		String[] ss = s.split(" ");
		int [] arr=new int [ss.length];
		for (int i = 0; i < arr.length; i++) {
			arr[i]=Integer.parseInt(ss[i]);
		}
		int[] num1=new int[s.length()];
		int[] num2=new int[s.length()];
		FindNumsAppearOnce(arr, num1, num2);
		FindNumsAppearOnce11(arr, num1, num2);
		FindNumsAppearOnce22(arr, num1, num2);
		FindNumsAppearOnce33(arr, num1, num2);
	}
}
